// 执行消耗内存为 10948 kb 的范例
#include <stdio.h>
#include <stdbool.h> // true

typedef struct
{
  int index;
  int data;
} node;

typedef struct
{
  node *element;
  int size;
} HashTable;

#define OK 0

HashTable *HashTableInit(int size)
{
  int ret;

  if (size <= 0)
  {
    return NULL;
  }

  HashTable *table = (HashTable *)malloc(sizeof(HashTable));
  if (table == NULL)
  {
    return NULL;
  }

  table->size = size;
  table->element = (node *)malloc(sizeof(node) * size);
  if (table->element == NULL)
  {
    free(table);
    return NULL;
  }

  memset(table->element, 0xff, sizeof(node) * size);
  return table;
}

int HashAddrGet(int data, int size)
{
  if (size == 0)
  {
    return 0;
  }
  int addr = data % size;
  return (addr >= 0) ? addr : addr + size;
}

void HashInsert(HashTable *table, int index, int data)
{
  int addr = HashAddrGet(data, table->size);

  while (table->element[addr].index != -1)
  {
    addr = (addr + 1) % table->size;
  }

  table->element[addr].index = index;
  table->element[addr].data = data;
  return;
}

node *HashFind(HashTable *table, int data)
{
  int addr = HashAddrGet(data, table->size);

  while (table->element[addr].index != -1)
  {
    if (table->element[addr].data == data)
    {
      return &table->element[addr];
    }
    addr = (addr + 1) % table->size;
  }
  return NULL;
}

void HashFree(HashTable *table)
{
  if (table == NULL)
  {
    return;
  }
  if (table->element != NULL)
  {
    free(table->element);
  }
  free(table);
  return;
}

#define MAX_TABLE_LEN 10000
int *twoSum(int *nums, int numsSize, int target, int *returnSize)
{
  int *ret = NULL;
  HashTable *table = NULL;
  node *node = NULL;
  ret = (int *)malloc(sizeof(int) * 2);
  table = HashTableInit(MAX_TABLE_LEN);
  for (int i = 0; i < numsSize; i++)
  {
    node = HashFind(table, target - nums[i]);
    if (node != NULL)
    {
      ret[0] = node->index;
      ret[1] = i;
      break;
    }
    HashInsert(table, i, nums[i]);
  }
  HashFree(table);
  *returnSize = 2;
  return ret;
}
